/***************************************************************************************************
  *Copyright(C),2010-2016,Sumscope
  *FileName	:  pinyin_search_engine2.cpp
  *Author	:  scofined.qi
  *Version	:  1.0
  *Date		:  2017/06/05
  *Desc		:  //用于主要说明此程序文件完成的主要功能
  *Relation :  
  *Others	:  //其他内容说明
  *Function :  //主要函数列表，每条记录应包含函数名及功能简要说明
  *History	:  //修改历史记录列表，每条修改记录应包含修改日期、修改者及修改内容简介
***************************************************************************************************/
#include "pinyin_search_engine2.h"
#include "pinyin_search_buffer.h"
#include "../pinyin.h"
#include "../../strings/string_page.h"
#include "../../strings/pinyin_search.h"
#include <core/strings/WideString.h>
#include <core/strings/BaseString.h>
#include <core/strings/string_convert.h>
#include <core/strings/string_util.h>
#include <core/container/CHashMap.h>
#include <core/container/hash_prime.h>
#include <core/system/memory.h>
#include <core/time/time.h>
#include <QTemporaryFile>
#include <QStandardPaths>
#include <QDir>
#include <algorithm>
#include <map>

#ifdef WIN32
#include <process.h>
#else
#include <sys/mman.h>
#include <fcntl.h>
#endif

#define ROUND_ALIGN(NUM, SIZE) ((NUM%SIZE==0)?NUM:((NUM/SIZE+1)*SIZE))
#define CHECK_MACRO(CODE)	//CODE;

#ifndef BASSERTS
#define BASSERTS //
#endif
#ifndef BASSERT
#define BASSERT //
#endif
#ifndef BVIEW
#define BVIEW //
#endif
#ifndef BLOGERR
#define BLOGERR //
#endif
#ifndef BS_METRICS
#define BS_METRICS //
#endif

namespace qb{
	namespace base{
		namespace internal{
			class SpellSearchMergedImpl : public ISpellSearch{
			private:
				struct InverseKey3{		// 取代wstring,减少内存开销
					typedef InverseKey3 ThisType;
					wchar_t	code[4];
				public:
					InverseKey3(){
						wchar_t*	pcode = code;
						*pcode++ = 0; *pcode++ = 0; *pcode++ = 0; *pcode++ = 0;
					}
					InverseKey3(const ThisType& ik){
						const wchar_t* str = ik.code;
						wchar_t*	pcode = code;
						*pcode++ = *str++; *pcode++ = *str++; *pcode++ = *str++;
						*pcode = 0;
					}
					InverseKey3(const wchar_t* str, int len){
						wchar_t*	pcode = code;
						*pcode++ = *str++; *pcode++ = *str++; *pcode++ = *str++;
						*pcode = 0;
					}
					unsigned int GetHash()const
					{
						return ((code[0] << 16) | code[1]) | (code[2] << 8);
					}
					ThisType& operator=(const ThisType& ik)
					{
						const wchar_t* str = ik.code;
						wchar_t*	pcode = code;
						*pcode++ = *str++; *pcode++ = *str++; *pcode++ = *str++;
						*pcode = 0;
						return *this;
					}
					bool operator==(const ThisType& ik)const{
						return code[0] == ik.code[0] && code[1] == ik.code[1] && code[2] == ik.code[2];
					}
					bool operator<(const ThisType& ik)const{
						return code[0] < ik.code[0] || code[1] < ik.code[1] || code[2] < ik.code[2];
					}
				};
				typedef InverseKey3 InverseKey;
				class InverseSet {
				public:
					typedef unsigned char uchar;
                    typedef std::map<int, uchar> Base;
					typedef Base::iterator iterator;
					typedef Base::const_iterator const_iterator;
				protected:
					Base		m_map;			// value 是一个债券的所有字段出现此key的个数,最大不会超过256
					int			m_max;			// 最大长度
				public:
					InverseSet() :m_max(1){}
					void reset(){ m_map.clear(); m_max = 0; }
					iterator begin(){ return m_map.begin(); }
					iterator end(){ return m_map.end(); }
					const_iterator cbegin()const{ return m_map.cbegin(); }
					const_iterator cend()const{ return m_map.cend(); }
					int size()const{ return m_map.size(); }
					int getmax()const{ return m_max; }
					bool empty()const{ return m_map.empty(); }
					void add(int key)
					{
						iterator it = m_map.find(key);
						if (it != m_map.end())
						{
							it->second++;
							m_max = m_max < it->second ? it->second : m_max;
						}
						else
							m_map.insert(Base::value_type(key, 1));
					}
					void remove(int key)
					{
						iterator it = m_map.find(key);
						if (it != m_map.end())
						{
							it->second--;
							if (it->second <= 0)
								m_map.erase(it);
						}
					}
					bool exist(int key)const
					{
						const_iterator it = m_map.find(key);
						return it != m_map.end();
					}
					void intersect(const InverseSet& op)
					{
						for (iterator it = begin(); it != end();)
						{
							if (!op.exist(it->first))
								it = m_map.erase(it);
							else
								++it;
						}
					}
					bool copy(int* indexes, int& capcity)
					{
						int* pint = indexes;
						int* pend = indexes + capcity;
						for (const_iterator it = m_map.begin(); it != m_map.end() && pint < pend; ++it)
						{
							*pint++ = it->first;
						}
						capcity = m_map.size();
						return true;
					}
				};
				class IndexIdRange {
				public:
					InverseSet*		m_memory_set;		// 内存中的集合
					int				m_offset;			// 在映射文件中的偏移量
					int				m_bytes;			// 
					int				m_length;			// 个数:24,8	高24位表示bid,低8位表示个数,对应InverseSet的key,value
				public:
					IndexIdRange(InverseSet* iset) :m_memory_set(iset), m_offset(0), m_length(0), m_bytes(0){}
				};
				class IndexIdStore{
					IndexId*		m_first;			// 按照bid递增
					int				m_count;			// 个数
					int				m_capcity;			// 容量
				public:
					IndexIdStore() :m_capcity(16), m_count(0), m_first(NULL){}
					~IndexIdStore(){ if (m_first)delete[] m_first; m_first = NULL; }
					void init(const InverseSet& iset)
					{
						resetcapcity(iset.size());
						for (InverseSet::const_iterator it = iset.cbegin(); it != iset.cend(); ++it)
						{
							m_first[m_count++] = (it->first << 8) | (it->second & 0x000000ff);
						}
					}
					void init(const IndexId* first, int count)
					{
						resetcapcity(count);
						for (int i = 0; i < count; i++)
							m_first[m_count++] = first[i];
					}
					void setcount(int ncount){ m_count = ncount; }
					int  count()const{ return m_count; }
					int	 get(int i){ return m_first[i]; }
					IndexId* first(){ return m_first; }
				protected:
					void resetcapcity(int capcity)
					{
						// 设置好capcity之后,不能使用>=m_cout的索引范围
						// 对于m_capcity很大,而此处的capcity很小的情况下
						// 将memset的参数调小,可以提升性能
						// 提升性能超级多,714ms ==> 4.740ms
						int num_set = capcity + 1;
						if (m_first == NULL || m_capcity < capcity)
						{
							if (m_first)	delete[] m_first;
							m_capcity = m_capcity < capcity ? capcity : m_capcity;
							m_first = new IndexId[m_capcity];
							num_set = m_capcity;
						}
						num_set = num_set >= m_capcity ? m_capcity : num_set;
						memset(m_first, 0, num_set*sizeof(IndexId));
						m_count = 0;
					}
				};
				class IndexIdVec {
					IndexId*		m_first;			// 按照bid递增
					int				m_count;			// 个数
					int				m_capcity;			// 容量
					IndexIdStore*	m_store;
				public:
					IndexIdVec() :m_first(0), m_count(0), m_capcity(0), m_store(0){}
					IndexIdVec(IndexId* first, int count, int capcity) : m_store(0){ bind(first, count, capcity); }

					void bind(IndexId* first, int count, int capcity){ m_first = first; m_count = count; m_capcity = capcity; }
					void copyfrom(const IndexIdVec& iivec)
					{
						memcpy(m_first, iivec.m_first, sizeof(IndexId)*m_count);
					}
					void copyfrom(const InverseSet& iset)
					{
						BASSERT(m_first && m_capcity >= iset.size());
						m_count = 0;
						for (InverseSet::const_iterator it = iset.cbegin(); it != iset.cend(); ++it)
						{
							m_first[m_count++] = makeid(it->first, it->second);
						}
					}
					void copyto(InverseSet& iset)
					{
						iset.reset();
						for (int i = 0; i < m_count; i++)
							iset.add(getkey(m_first[i]));
					}
					bool equal(const InverseSet& iset)const
					{
						if (m_count != iset.size())
							return false;
						if (m_count > 0 && m_first == NULL)
							return false;
						int i = 0;
						for (InverseSet::const_iterator it = iset.cbegin(); i < m_count && it != iset.cend(); ++it, ++i)
						{
							IndexId id = makeid(it->first, it->second);
							if (id != m_first[i])
								return false;
						}
						return true;
					}
					~IndexIdVec()
					{
					}
					int size()const{ return m_count; }
					bool add(int key)
					{
						//BASSERT(m_first && m_capcity > 0);
						int ipos = find(key);
						//BASSERT(ipos >= 0 && ipos <= m_count);
						IndexId* pid = m_first + ipos;
						if (ipos >= 0 && ipos < m_count)
						{
							if (getkey(*pid) == key)
							{
								*pid = makeid(key, getval(*pid) + 1);
								return true;
							}
						}

						// 将ipos后面的往后移动一个位置
						if (m_count >= m_capcity)
							return false;

						IndexId* source = m_first + m_count - 1;
						IndexId* dest = m_first + m_count;
						IndexId* end = m_first + ipos;
						//for (; source >= end;)
						//	*dest-- = *source--;
						if (m_count > ipos)
							memmove(m_first + ipos + 1, m_first + ipos, (m_count - ipos)*sizeof(IndexId));
						*pid = makeid(key, 1);
						m_count++;
						return true;
					}
					void remove(int key)
					{
						int ipos = find(key);
						if (ipos >= 0 && ipos < m_count)
						{
							IndexId* pid = m_first + ipos;
							if (getkey(*pid) != key)
								return;
							*pid = makeid(key, getval(*pid) - 1);
							if (getval(*pid) <= 0)
							{
								// 将后面的向前移动
								IndexId* dest = m_first + ipos;
								IndexId* source = m_first + ipos + 1;
								IndexId* end = m_first + m_count;
								//for (; source < end;)
								//	*dest++ = *source++;
								if (m_count > ipos + 1)
									memmove(dest, source, sizeof(IndexId)*(m_count - ipos - 1));
								m_count--;
							}
						}
					}
					void check()
					{
						if (m_first && m_count > 0)
						{
							int nerror = 0;
							int key = getkey(*m_first);
							for (int i = 1; i < m_count; i++)
							{
								if (key >= getkey(m_first[i]))
									nerror++;
							}
							BASSERTS(nerror <= 0, "nerror=%d", nerror);
						}
					}
					bool exist(int key)const
					{
						int ipos = find(key);
						if (ipos < 0 || ipos >= m_count)	return false;
						return getkey(m_first[ipos]) == key;
					}
					void clear()
					{
						if (m_first)
							m_first[0] = 0;
						m_count = 0;
					}
					void intersect(const InverseSet& iset)
					{
						int ncount = 0;
						for (int i = 0; i < m_count; i++)
						{
							if (iset.exist(getkey(m_first[i])))
							{
								m_first[ncount++] = m_first[i];
							}
						}
						m_count = ncount;
						if (m_capcity > m_count)
							memset(m_first + m_count, 0, (m_capcity - m_count) * sizeof(IndexId));
					}
					void intersect(const IndexIdVec& iis)
					{
						int ncount = 0;
						for (int i = 0; i < m_count; i++)
						{
							if (iis.exist(getkey(m_first[i])))
							{
								m_first[ncount++] = m_first[i];
							}
						}
						m_count = ncount;
						if (m_capcity > m_count)
							memset(m_first + m_count, 0, (m_capcity - m_count) * sizeof(IndexId));
					}
					bool empty()const{ return m_count <= 0; }
					const IndexId* first()const{ return m_first; }
					int count()const{ return m_count; }
					void transform()
					{
						if (m_first)
						{
							for (int i = 0; i < m_count; i++)
							{
								m_first[i] = getkey(m_first[i]);
							}
						}
					}
				protected:
#ifdef WIN32
					__forceinline IndexId makeid(int key, int val)const { return (key << 8) | (val & 0x000000ff); }
					__forceinline int getkey(IndexId ii)const { return (ii & 0xffffff00) >> 8; }
					__forceinline int getval(IndexId ii)const { return ii & 0x000000ff; }
#else
                    IndexId makeid(int key, int val)const { return (key << 8) | (val & 0x000000ff); }
                    int getkey(IndexId ii)const { return (ii & 0xffffff00) >> 8; }
                    int getval(IndexId ii)const { return ii & 0x000000ff; }
#endif
					int find(int key) const
					{
						//BASSERT(m_first);
						if (m_count <= 0 || key <= getkey(m_first[0]))
							return 0;
						if (key > getkey(m_first[m_count - 1]))
							return m_count;

						int left = 0, right = m_count, mid = 0;
						while (left + 4 < right)
						{
							mid = (left + right) >> 1;
							if (key < getkey(m_first[mid]))
								right = mid;
							else
								left = mid;
						}

						int i = left;
						for (; i < right; i++)
						{
							if (key <= getkey(m_first[i]))
								break;
						}
						return i;
					}
				};
				class IndexIdFile {
					enum{
						SIGNATURE = 0xFEFEABCD,
						MEGA_BYTES = 1024 * 1024,
					};
					struct KeyHead{
						int				m_offset;			// 在映射文件中的偏移量
						int				m_signature;		// 
						int				m_used;				// 已经使用的空间
						int				m_bytes;			// 整块内存大小
						int				m_capcity;			// 预留空间
						int				m_length;			// 个数:24,8	高24位表示bid,低8位表示个数,对应InverseSet的key,value
						wchar_t			m_key[4];			// 
					};
					struct Block{						// 代表空余空间
						int			bytes;
						bool		valid;
					public:
						Block() :bytes(0), valid(false){}
						Block(int b, bool v) :bytes(b), valid(v){}
					};
					class MappingView{							// 映射视图
						int			m_size;						// 视图大小，通常都是view size的倍数
						int			m_start;					// 在文件中的偏移量,是系统PAGE_SIZE的整数倍
						char*		m_view;						// 映射好的内存，后续需要解决使用试用一个内存地址去映射
						char*		m_last;						// 上一个m_view指针,用于绑定一个内存位置,反复使用
					public:
						MappingView() :m_size(0), m_start(0), m_view(0), m_last(0){}
						~MappingView(){}
						int GetStart()const{ return m_start; }
						int GetEnd()const{ return m_start + m_size; }
						int GetSize()const{ return m_size; }
						void Release()
						{
							m_last = m_view;
							if (m_view != NULL)
							{
#ifdef WIN32
                                UnmapViewOfFile(m_view);
                                MEMORY_BASIC_INFORMATION mbi;
                                memset(&mbi, 0, sizeof(mbi));
                                VirtualQuery(m_view, &mbi, sizeof(mbi));
#endif
							}
							m_view = NULL;
						}

                        bool Acquire(void* mapping, int start, int size)
						{
							BASSERT(mapping != NULL);
							m_start = start;
							m_size = size;

#ifdef WIN32
							if (m_last)
                                m_view = (char*)MapViewOfFileEx(mapping, FILE_MAP_READ | FILE_MAP_WRITE, 0, start, size, m_last);
							if (m_view == 0)
                                m_view = (char*)MapViewOfFileEx(mapping, FILE_MAP_READ | FILE_MAP_WRITE, 0, start, size, 0);

                            if (m_view == 0)
                            {
                                BVIEW("MapViewOfFileEx failed ,error:%d", GetLastError());
                            }
#else
                            m_view = (char*)((char*)mapping+start);
#endif
							return m_view != NULL;
						}

						const char* GetView()const{ return m_view; }
					};
					int				m_align_size;				// 每个KeyHad对应数据占据内存的大小对齐值,大小必须是此数字的整数倍
					float			m_reserve_ratio;			// 预留比例
					int				m_increase_size;			// 文件每次变大递增的尺寸,默认32mb
					int				m_sys_pagesize;				// 系统的页面大小,分配内存即按照此对齐

					int				m_cur_filesize;				// 当前映射文件大小,通常是m_increase_size的整数倍
					int				m_cur_usedsize;				// 已经使用的大小
#ifdef WIN32
                    void*			m_file;						// 文件句柄
#else
                    int             m_file;						// 文件句柄
#endif
                    void*			m_mapping;					// 映射文件句柄
					MappingView		m_view;						// 映射文件区域,随机映射区域
                    std::map<int, Block> m_blocks;					//

                    std::string		m_fname;					// 文件名称
				public:
                    IndexIdFile() :m_reserve_ratio(0.4f), m_align_size(256), m_cur_filesize(0), m_cur_usedsize(0)
					{
#ifdef WIN32
                        m_file = NULL;
#else
                        m_file = -1;
#endif
                        m_mapping = NULL;
                        m_sys_pagesize = qb::base::getMemPageSize();
						BASSERT(m_sys_pagesize > 0);

						m_increase_size = ROUND_ALIGN(MEGA_BYTES * 4, MEGA_BYTES);

                        QString strFileName = QDir::tempPath() + QDir::separator() + QString("QBS");
                        QTemporaryFile tmpFile(strFileName);
                        tmpFile.open();
                        tmpFile.close();
                        m_fname = strFileName.toStdString();

						Initialize(m_fname.c_str());
					}
					~IndexIdFile()
					{
						m_view.Release();

#ifdef WIN32
						if (m_mapping != NULL)
						{
							CloseHandle(m_mapping);
							m_mapping = NULL;
						}
						if (m_file != NULL)
						{
							SetFilePointer(m_file, 0, 0, FILE_BEGIN);
							SetEndOfFile(m_file);
							CloseHandle(m_file);
						}
						DeleteFileA(m_fname.c_str());
#else
                        if (m_mapping)
                        {
                            munmap(m_mapping, m_cur_filesize);
                            m_mapping = NULL;
                        }

                        if (m_file != -1)
                        {
                            if (m_file)
                            {
                                ftruncate(m_file, 0);
                            }
                            close(m_file);
                            m_file = -1;
                        }

                        if (!m_fname.empty())
                        {
                            remove(m_fname.c_str());
                        }
#endif
					}
				protected:
					bool Initialize(const char* fname)
					{
#ifdef WIN32
						DWORD fileattr = FILE_FLAG_SEQUENTIAL_SCAN | FILE_FLAG_WRITE_THROUGH;
						fileattr |= FILE_ATTRIBUTE_TEMPORARY | FILE_FLAG_DELETE_ON_CLOSE;
						m_file = CreateFileA(fname, GENERIC_WRITE | GENERIC_READ,
							0/*FILE_SHARE_READ*/, NULL, OPEN_ALWAYS, fileattr, NULL);
						if (m_file == INVALID_HANDLE_VALUE || m_file == NULL)
						{
							BLOGERR("failed to open file:%s error:%d", fname, GetLastError());
							return false;
						}
						SetFilePointer(m_file, 0, 0, FILE_BEGIN);
						SetEndOfFile(m_file);
#else
                        m_file = open(fname, O_RDWR | O_CREAT, S_IRUSR | S_IWUSR | S_IROTH | S_IWOTH);
                        if (m_file == -1)
                        {
                            return false;
                        }

                        ftruncate(m_file, 0);
#endif

						return true;
					}
					bool PrepareMapping(int maxSize)
					{
						BASSERT(maxSize%m_increase_size == 0);
						m_cur_filesize = maxSize;
                        BASSERT(m_mapping == NULL);

#ifdef WIN32
						DWORD flProtect = PAGE_READWRITE | SEC_COMMIT;
						m_mapping = CreateFileMapping(m_file, NULL, flProtect, 0, m_cur_filesize, NULL);
#else
                        ftruncate(m_file, m_cur_filesize);
                        m_mapping = mmap(0, m_cur_filesize, PROT_READ | PROT_WRITE, MAP_SHARED, m_file, 0);
#endif
                        if (m_mapping == NULL)
                            return false;

						return true;
					}
					void* AllocSpace(int bytes, int& offset)
					{
						BASSERT(bytes % m_align_size == 0 && bytes > 0);
						while (m_cur_usedsize + bytes > m_cur_filesize)
						{
							m_view.Release();
#ifdef WIN32
							CloseHandle(m_mapping);
#else
                            if (m_mapping)
                            {
                                munmap(m_mapping, m_cur_filesize);
                            }
#endif
                            m_mapping = NULL;
							if (!PrepareMapping(m_cur_filesize + m_increase_size))
							{
								BASSERTS(0, "PrepareMapping failed");
								return NULL;
							}
						}

						int start = ROUND_ALIGN(m_cur_usedsize, m_sys_pagesize);
						if (start > m_cur_usedsize)start -= m_sys_pagesize;
						int size = m_cur_usedsize + bytes - start;
						size = ROUND_ALIGN(size, m_sys_pagesize);
						m_view.Release();
						m_view.Acquire(m_mapping, start, size);
						char* mem = (char*)m_view.GetView();

						BASSERT(m_cur_usedsize - start >= 0);
						offset = m_cur_usedsize;
						m_cur_usedsize += bytes;
						return mem + (offset - start);
					}
					KeyHead* PrepareSpace(int offset, int bytes)
					{
						// 使得从偏移量offset开始的长度为bytes字节的内存可用
						BASSERT(offset >= 0 && bytes%m_align_size == 0 && bytes > 0 && offset + bytes <= m_cur_usedsize);
						if (m_view.GetView() == NULL ||
							offset<m_view.GetStart() ||
							offset + bytes>m_view.GetEnd())
						{
							m_view.Release();
							int start = ROUND_ALIGN(offset, m_sys_pagesize);
							if (start > offset)start -= m_sys_pagesize;
							int size = offset + bytes - start;
                            size = ROUND_ALIGN(size, m_sys_pagesize);
							m_view.Acquire(m_mapping, start, size);
						}
						BASSERT(m_view.GetView() != NULL);
						KeyHead* head = (KeyHead*)(m_view.GetView() + (offset - m_view.GetStart()));
						BASSERT(head->m_signature == SIGNATURE&& head->m_offset == offset && head->m_bytes == bytes);
						return head;
					}
				public:
					void Update(const InverseKey& key, IndexIdRange* iirange)
					{
						// 固定头部+变长记录+适度扩展区域40%
						BASSERT(iirange && iirange->m_memory_set != NULL);
						int bytes = sizeof(KeyHead) + (int)iirange->m_memory_set->size()*sizeof(IndexId)*(1 + m_reserve_ratio);
						bytes = ROUND_ALIGN(bytes, m_align_size);
						int offset = 0;
						void* memory = AllocSpace(bytes, offset);

						KeyHead* head = (KeyHead*)memory;
						head->m_offset = offset;
						head->m_signature = SIGNATURE;
						head->m_length = iirange->m_memory_set->size();
						head->m_used = head->m_length*sizeof(IndexId);
						head->m_bytes = bytes;
						head->m_capcity = (bytes - sizeof(KeyHead)) / sizeof(IndexId);
						memcpy(head->m_key, key.code, sizeof(key));

						IndexIdVec iivec((IndexId*)(head + 1), iirange->m_memory_set->size(), head->m_capcity);
						iivec.copyfrom(*iirange->m_memory_set);
						m_blocks[head->m_offset] = Block(head->m_bytes, true);

						iirange->m_bytes = head->m_bytes;
						iirange->m_offset = head->m_offset;
						iirange->m_length = head->m_length;
					}
					bool AddKey(IndexIdRange* iirange, int key)
					{
						BASSERT(iirange && iirange->m_bytes>0 && iirange->m_offset >= 0 && key >= 0);
						void* memory = PrepareSpace(iirange->m_offset, iirange->m_bytes);
						KeyHead* head = (KeyHead*)memory;
						BASSERT(head->m_signature == SIGNATURE&& head->m_offset == iirange->m_offset && head->m_bytes % m_align_size == 0);
						IndexIdVec iivec((IndexId*)(head + 1), head->m_length, head->m_capcity);
						if (!iivec.add(key))
						{
							BASSERT(head->m_length >= head->m_capcity);
							int bytes = head->m_bytes + (head->m_bytes >> 1);
							bytes = ROUND_ALIGN(bytes, m_align_size);
							int offset = 0;
							void* temp = new char[head->m_bytes];
							memcpy(temp, memory, head->m_bytes);
							void* newmemory = AllocSpace(bytes, offset);
							memcpy(newmemory, temp, head->m_bytes);
							delete[] temp;
							m_blocks[head->m_offset] = Block(head->m_bytes, false);

							head = (KeyHead*)newmemory;
							head->m_bytes = bytes;
							head->m_offset = offset;
							iivec.bind((IndexId*)(head + 1), head->m_length, head->m_capcity);
							iivec.add(key);
							m_blocks[head->m_offset] = Block(head->m_bytes, true);
						}
						head->m_length = iivec.size();
						head->m_used = head->m_length*sizeof(IndexId);
						iirange->m_offset = head->m_offset;
						iirange->m_bytes = head->m_bytes;
						iirange->m_length = iivec.size();
						BASSERT(head->m_used <= head->m_bytes && head->m_length <= head->m_capcity);
						return true;
					}
					bool RemoveKey(IndexIdRange* iirange, int key)
					{
						BASSERT(iirange && iirange->m_bytes>0 && key >= 0);
						void* memory = PrepareSpace(iirange->m_offset, iirange->m_bytes);
						KeyHead* head = (KeyHead*)memory;
						BASSERT(head->m_signature == SIGNATURE&& head->m_offset == iirange->m_offset && head->m_bytes % m_align_size == 0);
						IndexIdVec iivec((IndexId*)(head + 1), head->m_length, head->m_capcity);
						iivec.remove(key);
						head->m_length = iivec.size();
						head->m_used = head->m_length*sizeof(IndexId);
						iirange->m_length = iivec.size();
						BASSERT(head->m_used <= head->m_bytes && head->m_length <= head->m_capcity);
						return true;
					}
					bool GetIndexIdVec(const IndexIdRange* iirange, IndexIdVec& iivec)
					{
						BASSERT(iirange && iirange->m_bytes>0 && iirange->m_length>0);
						void* memory = PrepareSpace(iirange->m_offset, iirange->m_bytes);
						KeyHead* head = (KeyHead*)memory;
						BASSERT(head->m_offset == iirange->m_offset && head->m_bytes % m_align_size == 0);
						BASSERT(head->m_length == iirange->m_length && head->m_bytes == iirange->m_bytes && iirange->m_offset == head->m_offset);
						iivec.bind((IndexId*)(head + 1), head->m_length, head->m_capcity);
						return true;
					}
				};
				class IndexListMap
				{
				public:
                    typedef qb::base::CHashMap<InverseKey, IndexIdRange*>	InverseSetPtrHashMap;
					typedef InverseSetPtrHashMap::iterator iterator;
					typedef map < InverseKey, IndexIdRange* > InverseSetPtrMap;
				protected:
					InverseSetPtrHashMap	m_hashmap;			// 哈希表
					InverseSetPtrMap		m_ptrmap;			// 做对比测试使用
				public:
					IndexListMap(int capcity) :m_hashmap(capcity){}
					~IndexListMap()
					{
						InverseSetPtrHashMap::iterator it = m_hashmap.begin();
						for (; it != m_hashmap.end(); ++it)
						{
							const IndexIdRange* iirange = it.second();
							delete iirange;
						}
						m_hashmap.Clear();
						m_ptrmap.clear();
					}
					IndexIdRange* Find(const InverseKey& key)
					{
						IndexIdRange* pset = NULL;
						m_hashmap.Find(key, key.GetHash(), pset);
						return pset;
					}
					void Insert(const InverseKey& key, InverseSet* isets)
					{
						IndexIdRange* iirange = new IndexIdRange(isets);
						m_hashmap.Insert(key, key.GetHash(), iirange);
						m_ptrmap.insert(InverseSetPtrMap::value_type(key, iirange));
					}
					iterator begin(){ return m_hashmap.begin(); }
					iterator end(){ return m_hashmap.end(); }
					int size()const{ return m_hashmap.Count(); }
				};
				typedef ISpellSearchListener Listener;
			protected:
                typedef qb::base::strinfo strinfo;
                typedef qb::base::StringUtil StringUtil;
                typedef qb::base::HighResTime HighResTime;
                typedef qb::base::BaseString BaseString;
				typedef InverseSet	IndexSet;
				IndexListMap				m_indexes;		// key到IndexIdRange的映射关系
				InverseSet					m_firstset;		// 第一个键值搜索的结果集
				InverseSet					m_tempset;		// 第二个以及后续键值搜索的结果集
				IndexIdStore				m_firststore;	// 存储当前搜索的IndexId序列
                qb::base::CSLock			m_lock;			//
				int							m_keylen;		// 
				WideString					m_comma;		// 用于分隔pinyin.cpp产生的拼音串中间的逗号
				bool						m_initialized;	//
				bool						m_deleteset;
                qb::base::CConvertFast		m_convert;		// 用于转码
				IndexIdFile					m_file;			//
			public:
				SpellSearchMergedImpl() :m_keylen(3), m_initialized(false), m_deleteset(true),
                    m_indexes(qb::base::GetHashPrimeLargerThan(60000)), m_comma(L",")
				{
				}
				~SpellSearchMergedImpl()
				{

				}
				void Dump()
				{
					// 将size最大的前100个打印出来
					// 将max最大的前100个打印出来
					// key最多的前20个为:
					// ANG,111,HAN,NGC,GCD,HCD,行CD,CD0,YIN,NHA,INH,YHC,银行C,ONG,116,SHA,IAN,NGY,ING,001,HAI
					// AND:39306,HAI:11800
#define BVIEW_SIZE(ITEM)	BVIEW("sizeof(%s)\t=\t%d",#ITEM,sizeof(ITEM));
					//BVIEW_SIZE(InverseSet::Base::allocator_type);
					//BVIEW_SIZE(InverseSet::Base::value_type);
					//BVIEW_SIZE(InverseSet::Base::key_type);
					//BVIEW_SIZE(InverseSet::Base::mapped_type);
					//BVIEW_SIZE(InverseSet::Base::pointer);
					struct KeyInfo{
						InverseKey	key;
						int			size;
					};
                    std::vector<KeyInfo>	setvec;

					int sum_size = 0;
					int sum_memory = 0;
					int need_memory = 0;
					IndexListMap::iterator it = m_indexes.begin();
					for (; it != m_indexes.end(); ++it)
					{
						KeyInfo ki; ki.key = it.first();
						IndexIdRange* iirange = it.second();
						ki.size = iirange->m_memory_set ? iirange->m_memory_set->size() : iirange->m_length;
						setvec.push_back(ki);
						sum_size += ki.size;
						sum_memory += ki.size*sizeof(InverseSet::Base::value_type);
					}
					need_memory = sum_size*(sizeof(int) + sizeof(char)) + m_indexes.size()*sizeof(InverseKey);
					class ComparatorBySize{
					public:
						bool operator()(const KeyInfo& i1, const KeyInfo& i2)
						{
							return i1.size >= i2.size;
						}
					};


					BVIEW("ComparatorBySize 100,total:%d avgsize:%.2f  mem:%d  memneed:%6d", setvec.size(), sum_size*1.0 / setvec.size(), sum_memory, need_memory);
					std::sort(setvec.begin(), setvec.end(), ComparatorBySize());
					//for (int i = 0; i < 1000; i++)
					//{
					//	KeyInfo& ki = setvec[i];
					//	int nfound = 0;
					//	if (i < 100)
					//	{
					//		CBondContainer& bonds = *CBondContainer::instance();
					//		for (int k = 0; k < bonds.GetSize(); k++)
					//		{
					//			const CBondInfo& bond = bonds.ElementAt(k);
					//			if (IsBondMatch(bond, ki.key.code))
					//				nfound++;
					//		}
					//	}
					//	else
					//		nfound = ki.size;

					//	BVIEW("%3d\t%6s\tsize:%6d\tmax:%6d\tnfound:%6d\t%s", i, W2G(ki.key.code).c_str(), ki.size, 0, nfound,
					//		nfound != ki.size ? "************" : ""
					//		);
					//}
				}
				virtual void BuildIndex(bool diskless)override
				{
					if (m_initialized)
						return;
					BS_METRICS("[SPRIT_INIT] IndexIdFile");
					// 将内存的数据写入到映射文件中
					// 只将占用内存过大的写入到映射文件中:超过128个
					struct KeyInfo{
						InverseKey	key;
						IndexIdRange*	ptr;
					};
					vector<KeyInfo>	setvec;

					SCOPED_LOCK(m_lock);
					IndexListMap::iterator it = m_indexes.begin();
					for (; it != m_indexes.end(); ++it)
					{
						KeyInfo ki;
						ki.key = it.first();
						ki.ptr = it.second();
						setvec.push_back(ki);
					}
					class ComparatorBySize{
					public:
						bool operator()(const KeyInfo& i1, const KeyInfo& i2)
						{
							return i1.ptr->m_memory_set->size() >= i2.ptr->m_memory_set->size();
						}
					};
					std::sort(setvec.begin(), setvec.end(), ComparatorBySize());
					int mem_saved = 0, num_released = 0;
					for (int i = 0; i < (int)setvec.size(); i++)
					{
						KeyInfo& ki = setvec[i];
						if (ki.ptr->m_memory_set->size() < 128)
							break;
						m_file.Update(ki.key, ki.ptr);
						IndexIdVec iivec;
						m_file.GetIndexIdVec(ki.ptr, iivec);
						CHECK_MACRO(BASSERT(iivec.count() == ki.ptr->m_memory_set->size()));
						CHECK_MACRO(BASSERT(iivec.equal(*ki.ptr->m_memory_set)));

						mem_saved += ki.ptr->m_memory_set->size()*sizeof(InverseSet::Base::value_type) + sizeof(InverseSet);
						num_released++;
						if (m_deleteset)
						{
							delete ki.ptr->m_memory_set;
							ki.ptr->m_memory_set = NULL;
						}
					}

					for (int i = 0; i < (int)setvec.size(); i++)
					{
						KeyInfo& ki = setvec[i];
						IndexIdRange* iirange = m_indexes.Find(ki.key);
						if (iirange->m_memory_set != NULL)	continue;
						BASSERT(iirange && iirange->m_memory_set == NULL && iirange->m_offset >= 0 && iirange->m_bytes > 0);
						IndexIdVec iivec;
						m_file.GetIndexIdVec(iirange, iivec);
					}
					BVIEW("mem_saved:%d bytes, num_released:%d  keys:%d", mem_saved, num_released, setvec.size());
					m_initialized = true;
				}
				virtual void FindBonds(const wstring& text, Listener* listener)
				{
					IndexIdVec first;
					{
						SCOPED_LOCK(m_lock);
						IndexIdStore* store = ((int)text.size() >= m_keylen) ? UpdateFirstStore(InverseKey(text.c_str(), m_keylen)) : NULL;
						if (store)
							first.bind(store->first(), store->count(), store->count());
					int ncount = store ? store->count() : 0;
					//BVIEW("IndexIdSet[%2d] %s key:%s count:%5d result:%5d", 0, "vec",W2G(text.c_str(), 3).c_str(), ncount, ncount);
						for (int i = 1; !first.empty() && i + m_keylen <= (int)text.size(); i++)
						{
							InverseKey rkey(text.c_str() + i, m_keylen);
							IndexIdRange* iirange = m_indexes.Find(rkey);
							if (iirange == NULL)
							{
								first.clear();
								break;
							}
							if (iirange->m_memory_set)
						{
							first.intersect(*iirange->m_memory_set);
							//BVIEW("IndexIdSet[%2d] set key:%s count:%5d result:%5d", i, W2G(rkey.code, 3).c_str(),iirange->m_memory_set->size(),first.count());
						}
						else
						{
							IndexIdVec iivec;
							m_file.GetIndexIdVec(iirange, iivec);
							first.intersect(iivec);
							//BVIEW("IndexIdSet[%2d] vec key:%s count:%5d result:%5d", i, W2G(rkey.code, 3).c_str(), iivec.count(), first.count());
						}
						}
					}
					first.transform();
					BaseString gkey = W2G(text.c_str(), text.size());
					listener->OnResult((const int*)first.first(), first.count(), gkey.c_str(), gkey.size());

					//IndexIdStore* store = FindIndexBySpellMatch(text);
					//IndexIdVec first(store);
					//first.transform();
					//listener->OnResult((const int*)first.first(), first.count());
				}
				virtual bool AddBondChange(BondChangeBuffer* change)
				{
					if (change == NULL)
						return false;
					const int jian_size = 256;
					const int quan_size = 1024;
					int ncount = change->GetCount();
					SCOPED_LOCK(m_lock);
					for (int i = 0; i < ncount; i++)
					{
						const char* old = NULL;
						const char* now = NULL;
						kChangeType type = kChangeTypeName;
						int id = change->GetChange(i, type, old, now);
						switch (type)
						{
						case kChangeTypeName:
						{
							wchar_t jian[jian_size] = { 0 };
							wchar_t jian_now[jian_size] = { 0 };
							wchar_t quan[quan_size] = { 0 };
							wchar_t quan_now[quan_size] = { 0 };
							int jianlen = jian_size, quanlen = quan_size;
							int jianlen_now = jian_size, quanlen_now = quan_size;

							const wchar_t* oldw = m_convert.ToWide(old, strlen(old));
							Spell::Parse(oldw, m_convert.GetWstrSize(), quan, quanlen, jian, jianlen);
							const wchar_t* noww = m_convert.ToWide(now, strlen(now));
							Spell::Parse(noww, m_convert.GetWstrSize(), quan_now, quanlen_now, jian_now, jianlen_now);


							const wchar_t* tempkey = m_convert.ToWide(old, -1);
							RemoveIndexForSentence(id, tempkey, m_convert.GetWstrSize());
							RemoveIndexForSentence(id, jian, jianlen);
							RemoveIndexForSentence(id, quan, quanlen);


							tempkey = m_convert.ToWide(now, -1);
							AddIndexForSentence(id, tempkey, m_convert.GetWstrSize());
							AddIndexForSentence(id, jian_now, jianlen_now);
							AddIndexForSentence(id, quan_now, quanlen_now);
							break;
						}
						case kChangeTypeNameEn:
						case kChangeTypeCode:
						case kChangeTypeNameOnly:
						case kChangeTypePinyin:
						case kChangeTypePinyinFull:
						default:
						{
							const wchar_t* tempkey = m_convert.ToWide(old, -1);
							RemoveIndexForSentence(id, tempkey, m_convert.GetWstrSize());
							tempkey = m_convert.ToWide(now, -1);
							AddIndexForSentence(id, tempkey, m_convert.GetWstrSize());
							break;
						}
						}
					}
					return true;
				}
                virtual void GetAllKeys(std::vector<wstring>& keys)
				{
					SCOPED_LOCK(m_lock);
					IndexListMap::iterator it = m_indexes.begin();
					for (; it != m_indexes.end(); ++it)
					{
						keys.push_back(it.first().code);
					}
				}
			protected:
				InverseSet* FindInverseSet(const InverseKey& key, InverseSet* target)
				{
					IndexIdRange* iirange = m_indexes.Find(key);
					if (iirange == NULL)
						return NULL;
					if (iirange->m_memory_set)
						return iirange->m_memory_set;
					IndexIdVec iivec;
					m_file.GetIndexIdVec(iirange, iivec);
					iivec.copyto(*target);
					return target;
				}
				IndexIdStore* UpdateFirstStore(const InverseKey& key)
				{
					IndexIdRange* iirange = m_indexes.Find(key);
					if (iirange == NULL)
						return NULL;
					if (iirange->m_memory_set)
						m_firststore.init(*iirange->m_memory_set);
					else
					{
						IndexIdVec iivec;
						m_file.GetIndexIdVec(iirange, iivec);
						m_firststore.init(iivec.first(), iivec.count());
					}
					return &m_firststore;
				}
				IndexIdStore* FindIndexBySpellMatch(const wstring& text)
				{
					const wchar_t* name = text.c_str();
					int nlen = text.size();
					if (nlen < m_keylen)
						return NULL;

					SCOPED_LOCK(m_lock);
					InverseSet* first = FindInverseSet(InverseKey(name, m_keylen), &m_firstset);
					for (int i = 1; first && !first->empty() && i + m_keylen <= nlen; i++)
					{
						const InverseSet* pset = FindInverseSet(InverseKey(name + i, m_keylen), &m_tempset);
						if (pset == NULL)
                            return NULL;
						first->intersect(*pset);
					}
					m_firststore.init(*first);
					return &m_firststore;
				}
				void RemoveIndexForSentence(int index, const wchar_t* sentence, int len)
				{
					if (len <= 0)
						return;
					strinfo tokens[128] = { 0 };
					int tknum = StringUtil::SplitStringInfo(sentence, len, m_comma, tokens, 128);
					for (int i = 0; i < tknum; i++)
					{
						strinfo& token = tokens[i];
						if (token.len < m_keylen)
							continue;
						for (int j = 0; j + m_keylen <= token.len; j++)
						{
							RemoveIndexForKey(index, InverseKey(sentence + token.pos + j, m_keylen));
						}
					}
				}
				void RemoveIndexForKey(int index, const InverseKey& key)
				{
					IndexIdRange* iirange = m_indexes.Find(key);
					if (iirange)
					{
						if (iirange->m_memory_set)
							iirange->m_memory_set->remove(index);
						if (iirange->m_bytes>0)
							m_file.RemoveKey(iirange, index);
						
					}
				}
				void AddIndexForSentence(int index, const wchar_t* sentence, int len)
				{
					if (len <= 0)
						return;
					strinfo tokens[128] = { 0 };
					int tknum = StringUtil::SplitStringInfo(sentence, len, m_comma, tokens, 128);
					for (int i = 0; i < tknum; i++)
					{
						strinfo& token = tokens[i];
						if (token.len < m_keylen)
							continue;
						for (int j = 0; j + m_keylen <= token.len; j++)
						{
							AddIndexForKey(index, InverseKey(sentence + token.pos + j, m_keylen));
						}
					}
				}
				void AddIndexForKey(int index, const InverseKey& key)
				{
					//BASSERTS(wcslen(key.code) == 3, "");
					IndexIdRange* iirange = m_indexes.Find(key);
					InverseSet* pset = iirange ? iirange->m_memory_set : NULL;
					int bytes = iirange ? iirange->m_bytes : 0;
					if (bytes > 0)
					{
						m_file.AddKey(iirange, index);
					}

					if (pset)
					{
						pset->add(index);
						if (bytes > 0)
						{
							BASSERTS(iirange->m_length == pset->size(), "");
						}
					}
					else if ((bytes <= 0) || !m_deleteset)
					{
						pset = new InverseSet();
						pset->add(index);
						m_indexes.Insert(key, pset);
					}
				}
			};
			SpellSearchMerged::SpellSearchMerged()
			{
				m_impl = new SpellSearchMergedImpl();
			}

			SpellSearchMerged::~SpellSearchMerged()
			{
				if (m_impl)delete m_impl;
			}

			void SpellSearchMerged::BuildIndex(bool diskless)
			{
				m_impl->BuildIndex(diskless);
			}

			void SpellSearchMerged::FindBonds(const wstring& text, ISpellSearchListener* listener)
			{
				m_impl->FindBonds(text, listener);
			}

			bool SpellSearchMerged::AddBondChange(BondChangeBuffer* change)
			{
				return m_impl->AddBondChange(change);
			}

			void SpellSearchMerged::GetAllKeys(vector<wstring>& keys)
			{
				return m_impl->GetAllKeys(keys);
			}

		}
	}
}
